typedef char STDataType;

typedef struct Stack {
    STDataType* a;
    int top;
    int capacity;
} ST;

//
void STInit(ST* pst);
void STDestroy(ST* pst);
// 入栈和出栈
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);

// 取栈顶数据
STDataType STTop(ST* pst);
// 判空
bool STEmpty(ST* pst); // 头文件stdbool.h
// 获取数据个数
int STSize(ST* pst);

bool isValid(char* s) {
    ST st;
    STInit(&st);
    while (*s) {
        if (*s == '(' || *s == '[' || *s == '{') {
            STPush(&st, *s);
        } else {
            if (STEmpty(&st)) {
                STDestroy(&st);
                return false;
            }
            char top = STTop(&st);
            STPop(&st);

            // 不匹配
            if ((top == '(' && *s != ')') || (top == '[' && *s != ']') ||
                (top == '{' && *s != '}')) {
                return false;
            }
        }
        ++s;
    }
    /*if(!STEmpty(&st))
        return false;
    else
        return true;*/

    // 栈不为空，左括号多了，所以返回false
    bool ret = STEmpty(&st);
    STDestroy(&st);

    return ret;
}

// 初始化栈
void STInit(ST* pst) {
    assert(pst);

    pst->a = NULL;
    // top指向的是栈顶数据的下一个位置
    // 当top=0时，意味着没有数据，所以这时候指向下一位也就是0位置
    //   top=1时，开始指向第一位栈顶数据的下一个位置（也就是跟着的指针）
    //   top=2时，开始指向第二位栈顶数据的下一个位置......top=capacity时，就意味着栈已经满了
    pst->top = pst->capacity = 0;

    // top指向栈顶元素,没有元素时指向-1，若定义top=0，无法辨别top=0时是否有数据
    // pst->top = -1;
}

// 销毁栈
void STDestroy(ST* pst) {
    assert(pst);

    free(pst->a);
    pst->a = NULL;
    pst->top = pst->capacity = 0;
}

void STPush(ST* pst, STDataType x) {
    assert(pst);

    // 扩容
    if (pst->top == pst->capacity) {
        int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
        // 没有空间时，realloc有malloc的作用
        STDataType* tmp =
            (STDataType*)realloc(pst->a, newCapacity * sizeof(STDataType));
        if (NULL == tmp) {
            perror("realloc failed");
            return;
        }
        pst->a = tmp;
        pst->capacity = newCapacity;
    }

    pst->a[pst->top++] = x;
}

void STPop(ST* pst) {
    assert(pst);
    assert(pst->top > 0); // 栈为空时就不调用

    --pst->top;
}

STDataType STTop(ST* pst) {
    assert(pst);
    assert(pst->top > 0); // 栈为空时就不调用

    return pst->a[pst->top - 1];
}

// 判空
bool STEmpty(ST* pst) {
    assert(pst);

    return (pst->top == 0); // 0为空，非0为不空
}

// 获取数据个数
int STSize(ST* pst) {
    assert(pst);

    return pst->top;
}